package com.wangbo.sort;


/**
 * 快排
 */
public class QuickSort {

    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        // 基本情形
        if (L >= R) {
            return;
        }

        // 递归情形
        int[] boundaries = partition(arr, L, R);
        process(arr, L, boundaries[0]);
        process(arr, boundaries[1], R);

    }

    /**
     * 利用荷兰国旗问题，把数组三分，返回大于区和小于区的边界
     */
    public static int[] partition(int[] arr, int L, int R) {
        int p1 = L - 1; // 暂存指针，小于区右边界
        int p2 = R + 1; // 暂存指针，大于区左边界
        int p3 = L; // 遍历指针，从L移动到大于区左边界
        int num = arr[L + ((R - L) >> 1)]; // 划分值, 选取指定区间中的中间元素

        while (p3 < p2) {
            if (arr[p3] < num) {
                swap(arr, ++p1, p3++);
            } else if (arr[p3] == num) {
                p3++;
            } else {
                swap(arr, --p2, p3);
            }
        }

        return new int[]{p1, p2};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
